'''
@Descripttion: 
@version: 
@encoding: utf-8
@Author: qiurongcan
Date: 2025-08-29 17:42:00
LastEditTime: 2025-08-29 17:53:58
'''


# 合并K个升序列表

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next



class Solution:

    def mergeTwoLists(self, list1, list2):

        cur = dummy = ListNode()

        while list1 and list2:
            if list1.val < list2.val:
                cur.next = list1
                list1 = list1.next
            else:
                cur.next = list2
                list2 = list2.next
            cur = cur.next
        cur.next = list1 if list1 else list2
        return dummy.next



    def mergeKLists(self, lists):
        m = len(lists)
        if m == 0:
            return None
        if m == 1:
            return lists[0]
        left = self.mergeKLists(lists[:m // 2])
        right = self.mergeKLists(lists[m // 2:])
        
        return self.mergeTwoLists(left, right)



